class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[TreeNode]
        """
        node = head
        num = 0
        while node:
            node = node.next
            num += 1
        if num == 0:
            return None
        else:
            if num == 1:
                return TreeNode(head.val, None, None)
            else:
                if num == 2:
                    return TreeNode(head.val, None, TreeNode(head.next.val, None, None))
                else:
                    if num == 3:
                        return TreeNode(head.next.val, TreeNode(head.val, None, None), TreeNode(head.next.next.val, None, None))
                    else:
                        node = head
                        mid_num = int(num / 2)
                        index = 0
                        while index < mid_num - 1:
                            node = node.next
                            index += 1
                        mid_node = node.next
                        node.next = None
                        return TreeNode(mid_node.val, self.sortedListToBST(head), self.sortedListToBST(mid_node.next))
